노드 구조를 정의하고 핵심 포인터 연산의 효율성을 분석함으로써 링크드 리스트의 기초를 다집니다.
- 방금 관찰한 구조적 차이—특히 동적 포인터의 사용—은 자주 삽입과 삭제가 필요한 특정 응용 프로그램에서 링크드 리스트가 강력한 도구가 되게 합니다. 복잡한 알고리즘에 들어가기 전에, 이 구조의 정의와 핵심 메커니즘에 대한 단단한 기반을 마련해야 합니다.
- 이 강의 섹션은 링크드 리스트를 완전히 이해하는 데 집중합니다. 우리의 로드맵은 그 기본 개념과 고전적인 데이터 구조 문제에 대한 실용적 적용을 안내할 것입니다:
- 목표:n의 크기가 변동하거나 알 수 없을 때 링크드 리스트가 선택되는 이유를 이해하며, 효율성이 포인터 재연결보다는 메모리 이동에 달려 있다는 것을 이해합니다.
- 로드맵 개요:
- 1. 구조 및 정의: 우리는 공식적으로 노드 구조 (항목과 $next$ 포인터)를 정의하고, 단일, 이중, 순환 링크드 리스트 간의 차이를 살펴볼 것입니다.
- 2. 핵심 연산: 포인터 조작을 능숙하게 다루기:
- 순회: 리스트를 반복 탐색하며 $O(n)$ 시간이 필요합니다.
- 삽입: 알려진 위치 $i$에 노드를 추가하며, $next$ 포인터를 조정하여 효율적인 $O(1)$ 시간 내에 수행할 수 있습니다. 이때 포인터 재연결 색상에 달려 있다는 것을 이해합니다.
- 삭제: 노드를 제거하고 포인터를 조정하며, 이 역시 $O(1)$입니다.
- 3. 사례 적용 (다항식): 우리는 링크드 리스트를 이용해 대수적 다항식을 저장하고 조작할 것입니다. 각 노드는 다항식 항 ($\langle 계수, 지수 \rangle$)을 보유합니다. 이는 링크드 리스트가 동적 구조 관리에서 뛰어나며, 특히 다항식 덧셈에 있어 $O(n+m)$ 시간 내에 실행된다는 점을 보여줍니다.
링크드 리스트의 핵심 연산 복잡도
| 연산 | 설명 | 복잡도 |
|---|---|---|
| 순회 | 요소 또는 리스트의 끝을 찾는 것. | $O(n)$ |
| 삽입 (알려진 $i$ 위치) | 두 개의 포인터를 조정하는 것. | $O(1)$ |
| 삭제 (알려진 $i$ 위치) | 한 개의 포인터를 조정하는 것. | $O(1)$ |